package nlpeap.util.algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/** 
 * Union-Find Set
 * @author chuter
 *
 */
public class Unoin_Find_Set {
	
	private final int[] _father;
	private ArrayList<ArrayList<Integer>> unoin_set = new ArrayList<ArrayList<Integer>>();
	private HashSet<Integer> record = new HashSet<Integer>();
	
	public Unoin_Find_Set(int [] father_arr)
	{ 
		this._father = father_arr;
		if (!isValid(father_arr))
			throw new RuntimeException("the \"father_arr\" is unvalid!");
		unoin_set();
	}
	
	private boolean isValid(int[] int_arr)
	{
		int max = int_arr.length;
		for (int i = 0; i < int_arr.length; i++) {
			int v = int_arr[i];
			if (v >= max)
				return false;
			if (v < 0)
				int_arr[i] = i;
		}
		
		return true;
	}
	
	/** support circle instance */
	private int findFather(int index)
	{
		int father_id = _father[index];
		
		if (record.contains(father_id)) {
			_father[index] = index;
			return index;
		}
			
		if (father_id<0 || father_id==index)
			return index;
		else {
			record.add(index);
			father_id = findFather(_father[index]);
			_father[index] = father_id;
			record.remove(index);
			return father_id;
		}
	}
	
	private void unoin(int index_a, int index_b)
	{
		assert(record.isEmpty());
		int father_a = findFather(index_a);
		assert(record.isEmpty());
		int father_b = findFather(index_b);
		assert(record.isEmpty());
		if (father_a != father_b)
			_father[father_a] = father_b;
	}
	
	private void unoin_set()
	{		
		for (int i = 0; i < _father.length; i++)
			unoin(i, _father[i]);
		
		HashMap<Integer, Integer> unoin_set_map = new HashMap<Integer, Integer>();
		int set_num = 0;
		for (int i = 0; i < _father.length; i++) {
			int father_id = findFather(i); 
			if (unoin_set_map.containsKey(father_id)) {
				int set_id = unoin_set_map.get(father_id);
				unoin_set.get(set_id).add(i);
			} else {
				unoin_set_map.put(father_id, set_num);
				set_num++;
				
				ArrayList<Integer> chain = new ArrayList<Integer>();
				chain.add(i);
				unoin_set.add(chain);
			}
		}
	}
	
	public ArrayList<ArrayList<Integer>> getUnoinSet()
	{ return unoin_set; }
	
	//test program
	public static void main(String[] argv)
	{
		int[] test_arr = new int[]{
				3,1,4,5,4,7,-1,3,8,4
		};
		Unoin_Find_Set ins = new Unoin_Find_Set(test_arr);
		ArrayList<ArrayList<Integer>> uoin_set = ins.getUnoinSet();
		
		int uoin_id = 0;
		for (ArrayList<Integer> unoin : uoin_set) {
			System.out.println(String.format("Uoin %d:\n", uoin_id++));
			for (int item : unoin)
				System.out.print(item+" ");
			System.out.println("\n--------------------------------\n");
		}
	}
}
